/*
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true

执行用时 :28 ms, 在所有 C++ 提交中击败了43.88%的用户
内存消耗 :13.7 MB, 在所有 C++ 提交中击败了5.78%的用户
*/
#include <iostream>
#include <stack>
using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {};
};
class Solution {
	int midLen = 0;
public:
	//寻找给定链表的中间结点 奇数时正中间，偶数时中间靠左
	ListNode* midNode(ListNode* head) {
		if (head == NULL) {
			return NULL;
		}
		ListNode* chaster = head;
		ListNode* runner = head;
		while (runner) {
			
			if (runner->next == NULL || runner->next->next == NULL) {		//这个位置是有讲究的
				break;
			}
			midLen++;
			chaster = chaster->next;
			runner = runner->next->next;

		}
		return chaster;
	}
	bool isSame(ListNode* l1, ListNode* l2, int len) {	//别忘记=
		for (int i = 0; i <= len; i++) {				// 1 2 1 时长度是1，如果不带=，比较的是1 ，1 	这是对的
			if (l1->val != l2->val) {					//1 2 3 1 时长度也是1，如果不带=，比较的是 1， 1  但是这样就不行
				return false;							//这时带上=，分别比较的是1 2，1 2  和  1 2 ，1 3 这样就解决了这个问题
			}
			l1 = l1->next;
			l2 = l2->next;
		}
		return true;
	}
	ListNode* reverse(ListNode* head) {
		if (head == NULL) {
			return NULL;
		}
		else if (head->next == NULL) {
			return head;
		}

		ListNode* p1 = head;
		ListNode* p2 = p1->next;
		ListNode* p3 = p2->next;
		p1->next = NULL;
		if (p3 == NULL) {
			p2->next = p1;
			return p2;
		}
		while (p3->next) {
			p2->next = p1;
			p1 = p2;
			p2 = p3;
			p3 = p3->next;
		}
		p2->next = p1;
		p3->next = p2;
		return p3;
	}
	bool isPalindrome(ListNode* head) {
		if (head == NULL) {
			return true;
		}
		ListNode* mid = midNode(head);
		ListNode* l2 = reverse(mid);
		bool f = isSame(head, l2, midLen);
		return f;
	}
};

int main(int argc, char const* argv[])
{
	Solution s;
	int a[9] = { 1,3,5,7,9,7,5,3,1 };
	ListNode* cur = new ListNode(0);
	ListNode* dummy = cur;
	for (int i = 0; i < 9; i++) {
		ListNode* tmp = new ListNode(a[i]);
		cur->next = tmp;
		cur = tmp;
	}
	cout << s.isPalindrome(dummy->next) << endl;
	return 0;
}